package com.xhh.learning.record.algorithm.string;

/**
 * 类名： BmMatch
 * 描述：
 * 公司： 北京海鑫科金高科技股份有限公司
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/5/10 10:09
 * 最后修改时间:  2019/5/10 10:09
 */
public class BmMatch {

    public static void main(String[] args) {
        String str = "abaabaabbabaaabaabbabaab";
        String pStr = "abaabbabaab";

        int bf = bm(str, pStr);
        System.out.println(bf);
    }

    private static int bm(String str, String pStr) {
        if (str==null || "".equalsIgnoreCase(str.trim()) || pStr==null || "".equalsIgnoreCase(pStr.trim())) {
            return -1;
        }
        //记录模式串中每个字符最后出现的位置
        int[] bc = new int[256];
        char[] strArr = str.toCharArray();
        char[] pArr = pStr.toCharArray();
        // 构造坏字符哈希表
        generateBC(pArr, bc);
        int n = strArr.length;
        int m = pArr.length;
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGC(pArr, m, suffix, prefix);

        int i = 0;
        while (i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; j--) {
                if (pArr[j] != strArr[j + i]) {
                    break;
                }
            }

            if (j < 0) {
                return i;
            }

            int x = j - bc[(int)strArr[j + i]];
            int y = 0;
            if (j < m - 1) {
                y = moveGC(j, m, suffix, prefix);
            }

            if (y > x) {
                x = y;
            }

            i = i + x;
        }

        return -1;
    }

    private static void generateBC(char[] pArr, int[] bc) {

        for (int i = 0; i < bc.length; i++) {
            bc[i] = -1;
        }

        for (int i = 0; i < pArr.length; i++) {
            int ascii = (int) pArr[i];
            bc[ascii] = i;
        }
    }

    private static void generateGC(char[] pArr, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < suffix.length; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }

        for (int i = 0; i < m - 1; i++) {
            int j = i;
            int k = 0;// 公共后缀子串长度
            while (j >= 0 && pArr[j] == pArr[m - k - 1]) {
                j--;
                k++;
                suffix[k] = j + 1;//j+1 表示公共后缀子串在 b[0, i] 中的起始下标
            }

            if (j < 0) {
                prefix[k] = true;// 如果公共后缀子串也是模式串的前缀子串
            }
        }
    }

    public static int moveGC(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - j - 1;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }

        // [j+1,m-1]是好后缀字符串的下标范围,[j+2,m-1]是好后缀字符 子 串的下标范围
        for (int i = j + 2; i < m ; i++) {
            if (prefix[m - i]) {
                return i;
            }
        }
        return m;
    }


}

